#include <iostream>
#include <cmath>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr) {};
    ListNode(int x): val(x), next(nullptr) {};
};

void printListNode(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        cout << current->val << " ";
        current = current->next;
    }
    cout << "\n";
}

// 自己的方法，提交运行有报错
// 报错是因为 countA没有在定义是赋值，直接拿去使用了 :）
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    // 报错是因为 countA没有在定义是赋值，直接拿去使用了 :）
    int countA = 0, countB = 0;
    ListNode *currentA = headA, *currentB = headB;
    // 链表A长度
    while (currentA != nullptr) {
        countA++;
        currentA = currentA->next;
    }
    // 链表B长度
    while (currentB != nullptr) {
        countB++;
        currentB = currentB->next;
    }

    int gap = abs(countA - countB);
    currentA = headA;
    currentB = headB;
    if (countA > countB) {
        while (gap--) {
            currentA = currentA->next;
        }
    } else {
        while (gap--) {
            currentB = currentB->next;
        }
    }

    while (currentA != nullptr && currentB != nullptr) {
        if (currentA == currentB) {
            return currentA;
        }
        currentA = currentA->next;
        currentB = currentB->next;
    }

    return nullptr;
}

ListNode* getIntersectionNode2(ListNode* headA, ListNode* headB) {
    int countA = 0, countB = 0;
    ListNode *currentA = headA, *currentB = headB;
    // 链表A长度
    while (currentA != nullptr) {
        countA++;
        currentA = currentA->next;
    }
    // 链表B长度
    while (currentB != nullptr) {
        countB++;
        currentB = currentB->next;
    }

    currentA = headA;
    currentB = headB;

    // 让currentA为长链表的头，countA为其长度
    if (countB > countA) {
        swap(countA, countB);
        swap(currentA, currentB);
    }

    int gap = countA - countB;
    // 让currentA和currentB在同一起点（末尾位置对齐）
    while (gap--) {
        currentA = currentA->next;
    }

    while (currentA != nullptr) {
        if (currentA == currentB) {
            return currentA;
        }

        currentA = currentA->next;
        currentB = currentB->next;
    }

    return nullptr;
}

int main() {
    cout << "hello world..." << "\n";
    ListNode* node1 = new ListNode(2);
    ListNode* node2 = new ListNode(6);
    ListNode* node3 = new ListNode(4);
    node1->next = node2;
    node2->next = node3;

    ListNode* node33 = new ListNode(1);
    ListNode* node44 = new ListNode(5);
    node33->next = node44;

    cout << "origin1: " << "\n";
    printListNode(node1);

    cout << "origin2: " << "\n";
    printListNode(node33);

    ListNode* result = getIntersectionNode(node1, node33);
    cout << "result: " << "\n";
    printListNode(result);

    return 0;
}